home *** CD-ROM | disk | FTP | other *** search
/ Libris Britannia 4 / science library(b).zip / science library(b) / ELECTRON / PCB_DESI / 1540.ZIP / PCBCA110.ZIP / BOARD.C < prev    next >
C/C++ Source or Header  |  1990-01-07  |  7KB  |  266 lines
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include "cell.h"
  4.  
  5. #define LIMIT    ((unsigned long)0x00010000L)    /* 64k */
  6.  
  7. /* board dimensions */
  8. int Nrows = ILLEGAL;
  9. int Ncols = ILLEGAL;
  10.  
  11. int InitBoardDone = 0; /* sanity check */
  12.  
  13. /* memory usage */
  14. unsigned long Ltotal = 0; /* for board */
  15. unsigned long Itotal = 0; /* for dist */
  16. unsigned long Ctotal = 0; /* for dir */
  17.  
  18. /*
  19. ** memory is allocated in blocks of rows. as many rows as will fit in 64k are
  20. ** allocated in each block. blocks are linked together by pointers. the last
  21. ** block has a null 'next' pointer. if you want to route some *really* big
  22. ** boards (so big that 640k is not sufficient), you should change the
  23. ** algorithms below to test for Lotus-Intel-Microsoft expanded memory (LIM 3.2
  24. ** or 4.0) and use it if present. this would be a major enhancement, so if you
  25. ** do it i hope you will send it back to me so that it can be incorporated in
  26. ** future versions.
  27. */
  28.  
  29. struct lmem { /* a block of longs */
  30.     struct lmem far *next;     /* ptr to next block */
  31.     long         mem[1]; /* more than 1 is actually allocated */
  32.     };
  33.  
  34. struct imem { /* a block of ints */
  35.     struct imem far *next;     /* ptr to next block */
  36.     int         mem[1]; /* more than 1 is actually allocated */
  37.     };
  38.  
  39. struct cmem { /* a block of chars */
  40.     struct cmem far *next;     /* ptr to next block */
  41.     char         mem[1]; /* more than 1 is actually allocated */
  42.     };
  43.  
  44. struct lhead { /* header of blocks of longs */
  45.     int         numrows; /* number of rows per block */
  46.     struct lmem far *side[2]; /* ptr to first block of each chain */
  47.     };
  48.  
  49. struct ihead { /* header of blocks of ints */
  50.     int         numrows; /* number of rows per block */
  51.     struct imem far *side[2]; /* ptr to first block of each chain */
  52.     };
  53.  
  54. struct chead { /* header of blocks of chars */
  55.     int         numrows; /* number of rows per block */
  56.     struct cmem far *side[2]; /* ptr to first block of each chain */
  57.     };
  58.  
  59. static struct lhead Board = { 0, {NULL,NULL} }; /* 2-sided board */
  60. static struct ihead Dist = { 0, {NULL,NULL} }; /* path distance to cells */
  61. static struct chead Dir = { 0, {NULL,NULL} }; /* pointers back to source */
  62.  
  63. extern int JustBoard; /* boolean */
  64.  
  65. extern char far *Alloc( long );
  66.  
  67. void InitBoard( void );
  68. long GetCell( int, int, int );
  69. void SetCell( int, int, int, long );
  70. void OrCell( int, int, int, long );
  71. int GetDist( int, int, int );
  72. void SetDist( int, int, int, int );
  73. int GetDir( int, int, int );
  74. void SetDir( int, int, int, int );
  75.  
  76. void InitBoard () { /* initialize the data structures */
  77.     long lx, ly; /* for calculating block sizes */
  78.     struct lmem far * far *ltop;     /* for building board chain */
  79.     struct lmem far * far *lbottom;     /* for building board chain */
  80.     struct imem far * far *itop;     /* for building dist chain */
  81.     struct imem far * far *ibottom;     /* for building dist chain */
  82.     struct cmem far * far *ctop;     /* for building dir chain */
  83.     struct cmem far * far *cbottom;     /* for building dir chain */
  84.     int r, c, i, j, k; /* for calculating number of rows per block */
  85.  
  86.     if (Nrows <= 0 || Ncols <= 0) {
  87.         fprintf( stderr, "Nrows or Ncols is illegal\n" );
  88.         exit( -1 );
  89.         }
  90.     InitBoardDone = 1; /* we have been called */
  91. /* allocate Board (longs) */
  92.     for (lx = (long)Ncols*sizeof(long), ly = 0, i = 0;
  93.         i < Nrows && ly+lx <= (LIMIT - sizeof(long far *))
  94.             && ly+lx > ly; /* check for overflow */
  95.         ly += lx, i++)
  96.         ; /* calculate maximum number of rows per block */
  97.     if ((Board.numrows = i) <= 0) {
  98.         fprintf( stderr, "error: board too long\n" );
  99.         exit( -1 );
  100.         }
  101.     ltop = &(Board.side[TOP]);
  102.     lbottom = &(Board.side[BOTTOM]);
  103.     for (j = Nrows; j > 0; j -= i) {
  104.         k = (j > i) ? i : j;
  105.         ly = ((long)k * lx) + sizeof(long far *);
  106.         *ltop = (struct lmem far *)Alloc( ly );
  107.         *lbottom = (struct lmem far *)Alloc( ly );
  108.         Ltotal += 2*ly;
  109.         ltop = (struct lmem far * far *)(*ltop);
  110.         lbottom = (struct lmem far * far *)(*lbottom);
  111.         }
  112.     *ltop = *lbottom = NULL;
  113.     if (!JustBoard) {
  114. /* allocate Dist (ints) */
  115.         for (lx = (long)Ncols*sizeof(int), ly = 0, i = 0;
  116.             i < Nrows && ly+lx <= (LIMIT - sizeof(int far *))
  117.                 && ly+lx > ly; /* check for overflow */
  118.             ly += lx, i++)
  119.             ; /* calculate maximum number of rows per block */
  120.         if ((Dist.numrows = i) <= 0) {
  121.             fprintf( stderr, "error: board too long\n" );
  122.             exit( -1 );
  123.             }
  124.         itop = &(Dist.side[TOP]);
  125.         ibottom = &(Dist.side[BOTTOM]);
  126.         for (j = Nrows; j > 0; j -= i) {
  127.             k = (j > i) ? i : j;
  128.             ly = ((long)k * lx) + sizeof(int far *);
  129.             *itop = (struct imem far *)Alloc( ly );
  130.             *ibottom = (struct imem far *)Alloc( ly );
  131.             Itotal += 2*ly;
  132.             itop = (struct imem far * far *)(*itop);
  133.             ibottom = (struct imem far * far *)(*ibottom);
  134.             }
  135.         *itop = *ibottom = NULL;
  136. /* allocate Dir (chars) */
  137.         for (lx = (long)Ncols*sizeof(char), ly = 0, i = 0;
  138.             i < Nrows && ly+lx <= (LIMIT - sizeof(char far *))
  139.                 && ly+lx > ly; /* check for overflow */
  140.             ly += lx, i++)
  141.             ; /* calculate maximum number of rows per block */
  142.         if ((Dir.numrows = i) <= 0) {
  143.             fprintf( stderr, "error: board too long\n" );
  144.             exit( -1 );
  145.             }
  146.         ctop = &(Dir.side[TOP]);
  147.         cbottom = &(Dir.side[BOTTOM]);
  148.         for (j = Nrows; j > 0; j -= i) {
  149.             k = (j > i) ? i : j;
  150.             ly = ((long)k * lx) + sizeof(char far *);
  151.             *ctop = (struct cmem far *)Alloc( ly );
  152.             *cbottom = (struct cmem far *)Alloc( ly );
  153.             Ctotal += 2*ly;
  154.             ctop = (struct cmem far * far *)(*ctop);
  155.             cbottom = (struct cmem far * far *)(*cbottom);
  156.             }
  157.         *ctop = *cbottom = NULL;
  158.         }
  159. /* initialize everything to empty */
  160.     for (r = 0; r < Nrows; r++) {
  161.         for (c = 0; c < Ncols; c++) {
  162.             SetCell( r, c, TOP, (long)EMPTY );
  163.             SetCell( r, c, BOTTOM, (long)EMPTY );
  164.             if (!JustBoard) {
  165.                 SetDist( r, c, TOP, EMPTY );
  166.                 SetDist( r, c, BOTTOM, EMPTY );
  167.                 SetDir( r, c, TOP, FROM_NOWHERE );
  168.                 SetDir( r, c, BOTTOM, FROM_NOWHERE );
  169.                 }
  170.             }
  171.         }
  172.     }
  173.  
  174. long GetCell( r, c, s ) /* fetch board cell */
  175.     int r, c, s;
  176.     {
  177.     struct lmem far *p;
  178.  
  179.     p = Board.side[s];
  180.     while (r >= Board.numrows) {
  181.         p = p->next;
  182.         r -= Board.numrows;
  183.         }
  184.     return( p->mem[r*Ncols+c] );
  185.     }
  186.  
  187. void SetCell( r, c, s, x ) /* store board cell */
  188.     int r, c, s;
  189.     long x;
  190.     {
  191.     struct lmem far *p;
  192.  
  193.     p = Board.side[s];
  194.     while (r >= Board.numrows) {
  195.         p = p->next;
  196.         r -= Board.numrows;
  197.         }
  198.     p->mem[r*Ncols+c] = x;
  199.     }
  200.  
  201. void OrCell( r, c, s, x ) /* augment board cell */
  202.     int r, c, s;
  203.     long x;
  204.     {
  205.     struct lmem far *p;
  206.  
  207.     p = Board.side[s];
  208.     while (r >= Board.numrows) {
  209.         p = p->next;
  210.         r -= Board.numrows;
  211.         }
  212.     p->mem[r*Ncols+c] |= x;
  213.     }
  214.  
  215. int GetDist( r, c, s ) /* fetch distance cell */
  216.     int r, c, s;
  217.     {
  218.     struct imem far *p;
  219.  
  220.     p = Dist.side[s];
  221.     while (r >= Dist.numrows) {
  222.         p = p->next;
  223.         r -= Dist.numrows;
  224.         }
  225.     return( p->mem[r*Ncols+c] );
  226.     }
  227.  
  228. void SetDist( r, c, s, x ) /* store distance cell */
  229.     int r, c, s, x;
  230.     {
  231.     struct imem far *p;
  232.  
  233.     p = Dist.side[s];
  234.     while (r >= Dist.numrows) {
  235.         p = p->next;
  236.         r -= Dist.numrows;
  237.         }
  238.     p->mem[r*Ncols+c] = x;
  239.     }
  240.  
  241. int GetDir( r, c, s ) /* fetch direction cell */
  242.     int r, c, s;
  243.     {
  244.     struct cmem far *p;
  245.  
  246.     p = Dir.side[s];
  247.     while (r >= Dir.numrows) {
  248.         p = p->next;
  249.         r -= Dir.numrows;
  250.         }
  251.     return( (int)(p->mem[r*Ncols+c]) );
  252.     }
  253.  
  254. void SetDir( r, c, s, x ) /* store direction cell */
  255.     int r, c, s, x;
  256.     {
  257.     struct cmem far *p;
  258.  
  259.     p = Dir.side[s];
  260.     while (r >= Dir.numrows) {
  261.         p = p->next;
  262.         r -= Dir.numrows;
  263.         }
  264.     p->mem[r*Ncols+c] = (char)x;
  265.     }
  266.